package org.example;

import lombok.AllArgsConstructor;
import lombok.Data;

/**
 * 链表反转
 * @Auther: wangbw
 * @Date:2020/11/10
 * @Description: org.example
 * @version: 1.0
 */
public class LinkedList {
    @Data
    @AllArgsConstructor
    static class Node {
        private String data;
        private Node next;
    }

    /**
     * 递归法
     * @param head
     * @return
     */
    public static Node getReversalRecursion(Node head){
        if (head == null || head.next == null)
            return head;
        Node next = head.next;
        Node recursion = getReversalRecursion(next);
        next.setNext(head);
        head.setNext(null);
        return recursion;
    }

    /**
     * 头插法
     * @param head
     * @return
     */
    public static Node geReversal(Node head){
        Node pre = null;
        Node curTemp = head;
        Node tailTemp = head;
        while (curTemp != null){
            Node next = curTemp.next;
            curTemp.setNext(pre);
            pre = curTemp;
            curTemp  = next;
        }
        return pre;
    }

    public static void main(String[] args) {
        Node test = new Node("0", null);
        Node headtemp = test;
        for (int i = 1; i < 4; i++) {
            Node nextTemp = new Node(i + "", null);
            headtemp.setNext(nextTemp);
            headtemp = nextTemp;
        }
        print(test);
        Node head = geReversal(test);
        print(head);

    }

    static void print(Node headArg){
        Node head = headArg;
        while (head !=null){
            System.out.print(head.data + "  ->");
            head = head.next;
        }
        System.out.println("  null");
    }
}
